#include<stdio.h>
#include<stdlib.h>

#define MAX_VERTEX_NUM 20
#define True 1
#define False 0

//图的邻接矩阵存储结构定义
typedef struct
{
	int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵
	int vexnum;//顶点数
}Graph;

//队列结构定义
typedef struct
{
	int data[MAX_VERTEX_NUM];
	int front;
	int rear;
}Queue;

//初始化队列
void InitQueue(Queue *Q)
{
	Q->front=0;
	Q->rear=0;
}


//入队
void EnterQueue(Queue *Q,int x)
{
	Q->data[Q->rear++]=x;
}


//出队
void DeleteQueue(Queue *Q,int *x)
{
	*x=Q->data[Q->front++];
}


//判断队列是否为空
int Empty(Queue Q)
{
	return Q.front==Q.rear;
}

//访问顶点
void visit(int v)
{
	printf("%d",v);
}

//求顶点v的第一个邻接点
int FirstAdjVertex(Graph g,int v)
{
	for(int i=0;i<g.vexnum;i++)
	{
		if(g.arcs[v][i]!=0)
		{
			return i;
		}
	}
	return -1;
}

//求顶点v相对于邻接点w的下一个邻接点
int NextAdjVertex(Graph g,int v,int w)
{
	for(int i=w+1;i<g.vexnum;i++)
	{
		if(g.arcs[v][i]!=0)
		{
			return i;
		}
	}
	return -1;
}


//深度优先搜索遍历
void DepthFirstSearch(Graph g,int v0,int visited[])
{
	visit(v0);
	visited[v0]=True;
	int w=FirstAdjVertex(g,v0);
	while(w!=-1)
	{
		if(!visited[w])
		{
			DepthFirstSearch(g,w,visited);
		}
		w=NextAdjVertex(g,v0,w);
	}
}


//在图g中寻找未被访问的顶点作为起始点，并调用深度优先搜索过程进行遍历
void TraverseGraph(Graph g)
{
	int visited[MAX_VERTEX_NUM];
	for(int vi=0;vi<g.vexnum;vi++)
	{
		visited[vi]=False;
	}
	for(int vi=0;vi<g.vexnum;vi++)
	{
		if(!visited[vi]){DepthFirstSearch(g,vi,visited);}
	}
}

//广度优先搜索遍历
void BreadthFirstSearch(Graph g,int v0)
{
	int visited[MAX_VERTEX_NUM];
	for(int i=0;i<g.vexnum;i++)
	{
		visited[i]=False;
	}
	visit(v0);
	visited[v0]=True;
	Queue Q;
	InitQueue(&Q);
	EnterQueue(&Q,v0);
	while(!Empty(Q))
	{
		int v;
		DeleteQueue(&Q,&v);
		int w=FirstAdjVertex(g,v);
		while(w!=-1)
		{
			if(!visited[w])
			{
				visit(w);
				visited[w]=True;
				EnterQueue(&Q,w);
			}
			w=NextAdjVertex(g,v,w);
		}
	}
}

int main()
{
	Graph g;
	printf("请输入图的顶点数: ");
	scanf("%d", &g.vexnum);
	for(int i=0;i<g.vexnum;i++) 
	{
		for (int j=0;j<g.vexnum;j++) 
		{
			g.arcs[i][j]=0;
		}
	}
	printf("请依次输入邻接矩阵（用空格分隔，按行输入）:\n");
	for(int i=0;i<g.vexnum;i++) 
	{
		for (int j=0;j<g.vexnum;j++) 
		{
			scanf("%d", &g.arcs[i][j]);
		}
	}
	int choice,startVertex;
	while (1) {
		printf("\n请选择操作:\n");
		printf("1. 深度优先遍历整个图\n");
		printf("2. 广度优先搜索（请先输入起始顶点）\n");
		printf("0. 退出\n");
		scanf("%d", &choice);
		if (choice == 0) 
		{
			printf("退出程序\n");
			break;
		} 
		else if (choice == 1) 
		{
			printf("深度优先遍历结果为: ");
			TraverseGraph(g);
			printf("\n");
		} 
		else if (choice == 2) 
		{
			printf("请输入起始顶点: ");
			scanf("%d", &startVertex);
			if (startVertex < 0 || startVertex >= g.vexnum) 
			{
				printf("顶点编号无效\n");
			} 
			else 
			{
				printf("广度优先搜索结果为: ");
				BreadthFirstSearch(g, startVertex);
				printf("\n");
			}
		} else 
		{
			printf("无效的选择，请重新输入\n");
		}
	}
	return 0;
}
